//////////////////////////////////////////////////////////////////////
//
//	ZETeam source code 
//	Copyright (c) ZETeam 2011-..
//	
//	File: CMemoryAlloc.h
//  Description: Custom fast memory allocator.
// 
//	History:
//	- March 8, 2011: Created by Max Streltsov
//
//////////////////////////////////////////////////////////////////////

#ifndef __CMEMORY_ALLOC_H__
#define __CMEMORY_ALLOC_H__

#include "GSSystem_globals.h"

struct SMemFreeBlock;
typedef SMemFreeBlock * PMemFreeBlock;

struct SMemFreeBlock
{
	unsigned int _size;
	PMemFreeBlock _p_next;
};

const unsigned int kMaxHeapSize = 256 * 1024 * 1024; // 256Mb

class CMemoryHeap
{
public:

	~CMemoryHeap()
	{
		std::cout << std::endl << "in heap destruct" << std::endl;

		shutdown();
	};

	static CMemoryHeap & getInstance()
	{
		static CMemoryHeap heap_instance;
		
		return heap_instance;
	};

	bool init(unsigned int heap_size)
	{
		std::cout << std::endl << "in heap init" << std::endl;

		if (_is_inited)
		{
			//shutdown();

			return true;
		}

		if (heap_size < sizeof(PMemFreeBlock))
		{
			return false;
		}

		if (heap_size > kMaxHeapSize)
		{
			return false;
		}

		_heap_begin = (char*)malloc(heap_size);

		if (!_heap_begin)
		{
			return false;
		}

		_heap_size = heap_size;
		_num_allocs = 0;
		_mem_requested = 0;
		_mem_wasted = 0;
		_bad_allocs_num = 0;
		_num_requests = 0;
		_num_frees = 0;
		_mem_allocated = 0;

		_p_first_block = (PMemFreeBlock)_heap_begin;
		_p_first_block->_size = _heap_size;
		_p_first_block->_p_next = NULL;

		_is_inited = true;

		return true;
	};

	//simple allocation, puts length in first 4 bytes
	void * allocMem(unsigned int mem_size)
	{
		std::cout << std::endl << "in heap alloc mem" << std::endl;

		_num_requests++;

		unsigned int req_size = mem_size + sizeof(unsigned int); // lengh of block + block
		
		if (!_p_first_block || req_size > _heap_size)
		{
			_bad_allocs_num++;
			return NULL;
		}

		PMemFreeBlock found_block = _p_first_block;
		PMemFreeBlock prev_block = NULL;

		do
		{
			if (found_block->_size >= req_size)
			{
				break;
			}

			prev_block = found_block;
			found_block = found_block->_p_next;
			
		} while (found_block);
		
		if (!found_block)
		{
			_bad_allocs_num++;
			return NULL;
		}

		if (found_block->_size == req_size)
		{
			// if block is fully occupied, delete it from list
			if (prev_block)
			{
				prev_block->_p_next = found_block->_p_next;
			}
			else
			{
				_p_first_block = found_block->_p_next;
			}
		}
		else
		{
			// if not, strip it from the end by req_size bytes
			found_block->_size = found_block->_size - req_size;
		}

		_num_allocs++;
		_mem_requested += mem_size;
		_mem_wasted += sizeof(unsigned int);
		_mem_allocated += req_size;

		char * addr = (char *)found_block + found_block->_size;

		*(unsigned int *)(addr) = mem_size;
		return (void *)(addr + sizeof(unsigned int)); 
	};

	size_t freeMem(void * p_mem)
	{
		std::cout << std::endl << "in heap free mem" << std::endl;

		if (!p_mem || (p_mem < _heap_begin) || (p_mem > (_heap_begin + _heap_size)))
		{
			return 0;
		}

		char * p_req = (char *)p_mem - sizeof(unsigned int);

		unsigned int mem_size = *(unsigned int *)(p_req);
		
		unsigned int req_size = mem_size + sizeof(unsigned int);

		if (!_p_first_block)
		{
			_p_first_block = (PMemFreeBlock)p_req;
			_p_first_block->_p_next = NULL;
			_p_first_block->_size = req_size;
		}
		else
		{
			// find prev and next blocks
			
			PMemFreeBlock prev = NULL;
			PMemFreeBlock next = _p_first_block;

			while (next)
			{
				if ((char *)next >= p_req)
				{
					break;
				}

				prev = next;
				next = next->_p_next;
			}

			if ((char *)next == p_req)
			{
				// deleting already deleted block, skip
				return 0;
			}

			if (!prev)
			{
				// add at begining
				char * req_end = (char *)p_req + req_size;

				if ((char *)next == req_end)
				{
					((PMemFreeBlock)p_req)->_size = req_size + next->_size;
					((PMemFreeBlock)p_req)->_p_next = next->_p_next;
				}
				else
				{
					((PMemFreeBlock)p_req)->_size = req_size;
					((PMemFreeBlock)p_req)->_p_next = next;
				}

				_p_first_block = (PMemFreeBlock)p_req;
			}
			else
			{
				// add at end
				if (!next)
				{
					if (((char *)prev + prev->_size) == p_req)
					{
						prev->_size += req_size;
					}
					else
					{
						((PMemFreeBlock)p_req)->_size = req_size;
						((PMemFreeBlock)p_req)->_p_next = NULL;
						prev->_p_next = (PMemFreeBlock)p_req;
					}
				}
				else
				{
					char * prev_end = (char *)prev + prev->_size;
					char * next_begin = (char *)next;
					char * req_end = p_req + req_size;

					if (prev_end == p_req)
					{
						if (next_begin == req_end)
						{
							// merge 3 blocks
							prev->_size += req_size + next->_size;
							prev->_p_next = next->_p_next;
						}
						else
						{
							// merge prev + req
							prev->_size += req_size;
						}
					}
					else
					{
						if (next_begin == req_end)
						{
							// merge req + next
							((PMemFreeBlock)p_req)->_size = req_size + next->_size;
							((PMemFreeBlock)p_req)->_p_next = next->_p_next;
							prev->_p_next = (PMemFreeBlock)p_req;
						}
						else
						{
							// no merging, just insert between prev and next
							((PMemFreeBlock)p_req)->_size = req_size;
							((PMemFreeBlock)p_req)->_p_next = next;
							prev->_p_next = (PMemFreeBlock)p_req;
						}
					}

				}
			}
		}

		_num_frees++;
		_mem_requested -= mem_size;
		_mem_allocated -= req_size;
		_mem_wasted -= sizeof(unsigned int);

		return req_size;

	};

	void shutdown()
	{
		std::cout << std::endl << "!!!!!!! in heap shutdown" << std::endl;

		if (!_is_inited)
		{
			return;
		}

		if (_heap_begin)
		{
			free((void *)_heap_begin);
		}

		_heap_begin = NULL;
		_heap_size = 0;

		_is_inited = false;
	};

	std::string getInfo()
	{
		std::string info_str = "	Memory Manager info:...\n";

		return info_str;
	};

	void printInfo()
	{
		std::cout << "	Memory Manager info:" << std::endl;
		std::cout << "heap size = " << _heap_size << std::endl;
		std::cout << "num allocs = " << _num_allocs << std::endl;
		std::cout << "mem requested = " << _mem_requested << std::endl;
		std::cout << "mem wasted = " << _mem_wasted << std::endl;
		std::cout << "mem allocated = " << _mem_allocated << std::endl;
		std::cout << "bad allocs_num = " << _bad_allocs_num << std::endl;
		std::cout << "num requests = " << _num_requests << std::endl;
		std::cout << "num frees = " << _num_frees << std::endl;
		std::cout << std::endl;
		std::cout << "free blocks info:" << std::endl;

		PMemFreeBlock curr = _p_first_block;
		unsigned int counter = 1;

		while (curr)
		{
			std::cout << 
				"block " << counter << " size " << curr->_size
									<< " pos " << curr << std::endl;

			curr = curr->_p_next;
			counter++;
		}
	}

protected:

private:

	CMemoryHeap():
		_heap_size(0),
		_heap_begin(NULL),
		_num_allocs(0),
		_mem_requested(0),
		_mem_wasted(0),
		_num_requests(0),
		_bad_allocs_num(0),
		_num_frees(0),
		_mem_allocated(0),
		_p_first_block(NULL),
		_is_inited(false)
	{

	};

	unsigned int _heap_size;
	unsigned int _num_allocs;
	unsigned int _mem_requested;
	unsigned int _mem_wasted;
	unsigned int _mem_allocated;
	unsigned int _bad_allocs_num;
	unsigned int _num_requests;
	unsigned int _num_frees;

	PMemFreeBlock _p_first_block;

	char * _heap_begin;
	bool _is_inited;
};

#endif // #ifndef __CMEMORY_ALLOC_H__